package chapter2_complex;

/**
 * 数组实现的队列 先进先出
 */
public class ArrayQueue<T> {

    /**
     * 数组元素
     */
    private T[] data;
    /**
     * 指向头的指针
     */
    private int head;
    /**
     * 指向尾的指针
     */
    private int tail;
    /**
     * 容量
     */
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        data = (T[]) new Object[capacity];
    }

    public ArrayQueue() {
        this(10);
    }

    /**
     * 插入
     *
     * @param e
     */
    public void offer(T e) {
        if (tail + 1 == data.length) {
            resize(data.length * 2);
        }
        data[tail++] = e;
    }

    /**
     * 移除
     *
     * @return
     */
    public T take() {
        T e = data[head++];
        if (tail - head == data.length / 4) {
            resize(data.length / 2);
        }
        return e;
    }

    public boolean isEmpty() {
        return tail - head == 0;
    }

    /**
     * 变换大小
     *
     * @param length
     */
    private void resize(int length) {
        T[] newArray = (T[]) new Object[length];
        System.arraycopy(data, head, newArray, 0, tail - head);
        if (data.length > newArray.length) {
            tail -= head;
        }
        data = newArray;
        head = 0;
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 0; i < 150; i++) {
            queue.offer(i);
        }

        while (!queue.isEmpty()) {
            System.out.print(queue.take() + ",");
        }
    }


}
